lib/Mi manual de algoritmos/version_actual/src/geometria/monotonechain.tex

   1 % Generator: GNU source-highlight, by Lorenzo Bettini, http://www.gnu.org/software/src-highlite
   2
   3 {\ttfamily \raggedright {
   4 \noindent
   5 \mbox{}\textit{\textcolor{Brown}{//\ Implementation\ of\ Monotone\ Chain\ Convex\ Hull\ algorithm.}} \\
   6 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$algorithm$>$}} \\
   7 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$vector$>$}} \\
   8 \mbox{}\textbf{\textcolor{Blue}{using}}\ \textbf{\textcolor{Blue}{namespace}}\ std\textcolor{BrickRed}{;} \\
   9 \mbox{}\  \\
  10 \mbox{}\textbf{\textcolor{Blue}{typedef}}\ \textcolor{ForestGreen}{long}\ \textcolor{ForestGreen}{long}\ CoordType\textcolor{BrickRed}{;} \\
  11 \mbox{}\  \\
  12 \mbox{}\textbf{\textcolor{Blue}{struct}}\ Point\ \textcolor{Red}{\{} \\
  13 \mbox{}\ \ \ \ \ \ \ \ CoordType\ x\textcolor{BrickRed}{,}\ y\textcolor{BrickRed}{;} \\
  14 \mbox{}\  \\
  15 \mbox{}\ \ \ \ \ \ \ \ \textcolor{ForestGreen}{bool}\ \textbf{\textcolor{Blue}{operator}}\ \textcolor{BrickRed}{$<$(}\textbf{\textcolor{Blue}{const}}\ Point\ \textcolor{BrickRed}{\&}p\textcolor{BrickRed}{)}\ \textbf{\textcolor{Blue}{const}}\ \textcolor{Red}{\{} \\
  16 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{return}}\ x\ \textcolor{BrickRed}{$<$}\ p\textcolor{BrickRed}{.}x\ \textcolor{BrickRed}{$|$$|$}\ \textcolor{BrickRed}{(}x\ \textcolor{BrickRed}{==}\ p\textcolor{BrickRed}{.}x\ \textcolor{BrickRed}{\&\&}\ y\ \textcolor{BrickRed}{$<$}\ p\textcolor{BrickRed}{.}y\textcolor{BrickRed}{);} \\
  17 \mbox{}\ \ \ \ \ \ \ \ \textcolor{Red}{\}} \\
  18 \mbox{}\textcolor{Red}{\}}\textcolor{BrickRed}{;} \\
  19 \mbox{}\  \\
  20 \mbox{}\textit{\textcolor{Brown}{//\ 2D\ cross\ product.}} \\
  21 \mbox{}\textit{\textcolor{Brown}{//\ Return\ a\ positive\ value,\ if\ OAB\ makes\ a\ counter-clockwise\ turn,}} \\
  22 \mbox{}\textit{\textcolor{Brown}{//\ negative\ for\ clockwise\ turn,\ and\ zero\ if\ the\ points\ are\ collinear.}} \\
  23 \mbox{}CoordType\ \textbf{\textcolor{Black}{cross}}\textcolor{BrickRed}{(}\textbf{\textcolor{Blue}{const}}\ Point\ \textcolor{BrickRed}{\&}O\textcolor{BrickRed}{,}\ \textbf{\textcolor{Blue}{const}}\ Point\ \textcolor{BrickRed}{\&}A\textcolor{BrickRed}{,}\ \textbf{\textcolor{Blue}{const}}\ Point\ \textcolor{BrickRed}{\&}B\textcolor{BrickRed}{)} \\
  24 \mbox{}\textcolor{Red}{\{} \\
  25 \mbox{}\ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{return}}\ \textcolor{BrickRed}{(}A\textcolor{BrickRed}{.}x\ \textcolor{BrickRed}{-}\ O\textcolor{BrickRed}{.}x\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{*}\ \textcolor{BrickRed}{(}B\textcolor{BrickRed}{.}y\ \textcolor{BrickRed}{-}\ O\textcolor{BrickRed}{.}y\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{-}\ \textcolor{BrickRed}{(}A\textcolor{BrickRed}{.}y\ \textcolor{BrickRed}{-}\ O\textcolor{BrickRed}{.}y\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{*}\ \textcolor{BrickRed}{(}B\textcolor{BrickRed}{.}x\ \textcolor{BrickRed}{-}\ O\textcolor{BrickRed}{.}x\textcolor{BrickRed}{);} \\
  26 \mbox{}\textcolor{Red}{\}} \\
  27 \mbox{}\  \\
  28 \mbox{}\textit{\textcolor{Brown}{//\ Returns\ a\ list\ of\ points\ on\ the\ convex\ hull\ in\ counter-clockwise\ order.}} \\
  29 \mbox{}\textit{\textcolor{Brown}{//\ Note:\ the\ last\ point\ in\ the\ returned\ list\ is\ the\ same\ as\ the\ first\ one.}} \\
  30 \mbox{}vector\textcolor{BrickRed}{$<$}Point\textcolor{BrickRed}{$>$}\ \textbf{\textcolor{Black}{convexHull}}\textcolor{BrickRed}{(}vector\textcolor{BrickRed}{$<$}Point\textcolor{BrickRed}{$>$}\ P\textcolor{BrickRed}{)} \\
  31 \mbox{}\textcolor{Red}{\{} \\
  32 \mbox{}\ \ \ \ \ \ \ \ \textcolor{ForestGreen}{int}\ n\ \textcolor{BrickRed}{=}\ P\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{size}}\textcolor{BrickRed}{(),}\ k\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
  33 \mbox{}\ \ \ \ \ \ \ \ vector\textcolor{BrickRed}{$<$}Point\textcolor{BrickRed}{$>$}\ \textbf{\textcolor{Black}{H}}\textcolor{BrickRed}{(}\textcolor{Purple}{2}\textcolor{BrickRed}{*}n\textcolor{BrickRed}{);} \\
  34 \mbox{}\  \\
  35 \mbox{}\ \ \ \ \ \ \ \ \textit{\textcolor{Brown}{//\ Sort\ points\ lexicographically}} \\
  36 \mbox{}\ \ \ \ \ \ \ \ \textbf{\textcolor{Black}{sort}}\textcolor{BrickRed}{(}P\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{begin}}\textcolor{BrickRed}{(),}\ P\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{end}}\textcolor{BrickRed}{());} \\
  37 \mbox{}\  \\
  38 \mbox{}\ \ \ \ \ \ \ \ \textit{\textcolor{Brown}{//\ Build\ lower\ hull}} \\
  39 \mbox{}\ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\ \textcolor{BrickRed}{$<$}\ n\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{++)}\ \textcolor{Red}{\{} \\
  40 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{while}}\ \textcolor{BrickRed}{(}k\ \textcolor{BrickRed}{$>$=}\ \textcolor{Purple}{2}\ \textcolor{BrickRed}{\&\&}\ \textbf{\textcolor{Black}{cross}}\textcolor{BrickRed}{(}H\textcolor{BrickRed}{[}k\textcolor{BrickRed}{-}\textcolor{Purple}{2}\textcolor{BrickRed}{],}\ H\textcolor{BrickRed}{[}k\textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{],}\ P\textcolor{BrickRed}{[}i\textcolor{BrickRed}{])}\ \textcolor{BrickRed}{$<$=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{)}\ k\textcolor{BrickRed}{-\/-;} \\
  41 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ H\textcolor{BrickRed}{[}k\textcolor{BrickRed}{++]}\ \textcolor{BrickRed}{=}\ P\textcolor{BrickRed}{[}i\textcolor{BrickRed}{];} \\
  42 \mbox{}\ \ \ \ \ \ \ \ \textcolor{Red}{\}} \\
  43 \mbox{}\  \\
  44 \mbox{}\ \ \ \ \ \ \ \ \textit{\textcolor{Brown}{//\ Build\ upper\ hull}} \\
  45 \mbox{}\ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\ \textcolor{BrickRed}{=}\ n\textcolor{BrickRed}{-}\textcolor{Purple}{2}\textcolor{BrickRed}{,}\ t\ \textcolor{BrickRed}{=}\ k\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{;}\ i\ \textcolor{BrickRed}{$>$=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{-\/-)}\ \textcolor{Red}{\{} \\
  46 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{while}}\ \textcolor{BrickRed}{(}k\ \textcolor{BrickRed}{$>$=}\ t\ \textcolor{BrickRed}{\&\&}\ \textbf{\textcolor{Black}{cross}}\textcolor{BrickRed}{(}H\textcolor{BrickRed}{[}k\textcolor{BrickRed}{-}\textcolor{Purple}{2}\textcolor{BrickRed}{],}\ H\textcolor{BrickRed}{[}k\textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{],}\ P\textcolor{BrickRed}{[}i\textcolor{BrickRed}{])}\ \textcolor{BrickRed}{$<$=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{)}\ k\textcolor{BrickRed}{-\/-;} \\
  47 \mbox{}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ H\textcolor{BrickRed}{[}k\textcolor{BrickRed}{++]}\ \textcolor{BrickRed}{=}\ P\textcolor{BrickRed}{[}i\textcolor{BrickRed}{];} \\
  48 \mbox{}\ \ \ \ \ \ \ \ \textcolor{Red}{\}} \\
  49 \mbox{}\  \\
  50 \mbox{}\ \ \ \ \ \ \ \ H\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{resize}}\textcolor{BrickRed}{(}k\textcolor{BrickRed}{);} \\
  51 \mbox{}\ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{return}}\ H\textcolor{BrickRed}{;} \\
  52 \mbox{}\textcolor{Red}{\}} \\
  53
  54 } \normalfont\normalsize